/**
 * 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.
 *
 * Find the sum of all numbers which are equal to the sum of the factorial 
 * of their digits.
 *
 * Note: as 1! = 1 and 2! = 2 are not sums they are not included.
 *
 * ANSWER: 40730.
 *
 * NOTE: This problem is similar to problem 30.
 */

#include <iostream>
// #include <algorithm>

static const int fact[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

static int sum_fact_digits(int n)
{
	int sum = 0;
	while (n > 0)
	{
		int d = n % 10;
		sum += fact[d];
		n /= 10;
	}
	return sum;
}

void solve_problem_34()
{
	int total = 0;
	for (int n = 10; n <= fact[9]*7; n++)
	{
		if (n == sum_fact_digits(n))
		{
			//std::cout << n << std::endl;
			total += n;
		}
	}
	std::cout << total << std::endl;
}

#if 0
static int sort_digits(int n)
{
	int digits[100];
	int count = 0;
	while (n > 0)
	{
		digits[count++] = n % 10;
		n /= 10;
	}

	std::sort(digits + 0, digits + count);
	n = 0;
	for (int i = 0; i < count; i++)
	{
		n = n * 10 + digits[i];
	}
	return n;
}

static int find_numbers(int ndigits, int current, int partial_sum, int zeros, const int fact[10])
{
	int start = current % 10;
	current *= 10;

	int sum = 0;
	if (ndigits == 1)
	{
		for (int d = start; d <= 9; d++)
		{
			int s = partial_sum + fact[d];
			for (int z = 0; z <= (zeros+(d==0)?1:0); z++)
			{
				if (sort_digits(s - z) == current + d)
				{
					std::cout << "Found " << (s - z) << std::endl;
					sum += (s - z);
				}
			}
		}
	}
	else
	{
		for (int d = start; d <= 9; d++)
		{
			sum += find_numbers(ndigits-1, current + d, partial_sum+fact[d],
				(d == 0)? zeros+1 : zeros, fact);
		}
	}
	return sum;
}

static const int fact[10] = { 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880 };

void solve_problem_34()
{
	const int M = 7; // maximum possible is 7-digit number

	// Find the sum of all such numbers, excluding 1 and 2.
	int sum = find_numbers(M, 0, 0, 0, fact);
	// std::cout << (sum - 1) << std::endl;
}

#endif
